package algorithm.array;

import java.util.Arrays;

/**
 * leetcode : https://leetcode.com/problems/merge-sorted-array/description/
 * Diffculty: Easy
 *
 * 思路：
 * 如果从前往后的话，那插入num1数组，需要把整体元素向后移。
 * 那么就换一个思路，在 num1 从后往前插入元素，最后的index为 m+n-1.
 *
 *
 * @Author Antony
 * @Since 2018/7/5 11:05
 */
public class MergeSortedArray {

    public static void main(String[] args) {
        int[] num_1 = new int[]{2,0};
        int[] num_2 = new int[]{1};

        merge(num_1,1,num_2,1);
        System.out.println(Arrays.toString(num_1));
    }

    // (leetcode beats 100.00%)
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int tail_index = m+n-1;
        while(n > 0 && m > 0){
            if(nums1[m-1] < nums2[n-1]){
                nums1[tail_index--] = nums2[--n];
            }else{
                nums1[tail_index--] = nums1[--m];
            }
        }

        // 下面是处理其中一个元素完了另一个还没完的情况
        while(n > 0){
            nums1[tail_index--] = nums2[--n];
        }
        while(m > 0){
            nums1[tail_index--] = nums1[--m];
        }
    }
}
